Chuyến bay đầu tiên trên khu vực sân bay Reykjavík hiện nay diễn ra ngày 3.9.1919 khi máy bay Avro 504, máy bay đầu tiên của Iceland cất cánh[3]. Sân bay hiện nay do quân đội Anh xây dựng trong thời Thế chiến thứ hai trên bờ phía nam của bán đảo Reykjavík, khi đó Reykjavík chỉ là 1 thành phố nhỏ. Quân đội Anh bắt đầu xây sân bay từ tháng 10/1940, lúc đó sân bay chỉ là bãi cỏ.

Sau khi chiến tranh chấm dứt, quân đội Anh trao sân bay lại cho chính phủ Iceland ngày 6.7.1946 và từ đó, sân bay này do Cơ quan hàng không dân dụng Iceland (nay gọi là Flugstoðir) quản lý.

Trong các thập niên sau, thành phố Reykjavík phát triển quanh sân bay, và nay sân bay nằm ở phần phía tây của thành phố. Việc đổi mới sân bay bắt đầu từ năm 2000 và kéo dài 2 năm. Sau khi đổi mới, chiều rộng của phi đạo số 01/19 và 13/31 là 45 m, và chiều rộng của phi đạo 06/24 là 30m.

Năm 2001, có cuộc trưng cầu ý dân về việc nên hay không nên dời sân bay đi nơi khác, vì ở quá sát thành phố thủ đô. Trong cuộc trưng cầu ý dân này 49,3% người đồng ý dời và 48,1% người không đồng ý và yêu cầu tạm chờ tới năm 2016, khi kế hoạch mở rộng đô thị được hoàn tất.